/**
 * 双指针法
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
export var twoSum = function (numbers, target) {
  let index1 = 0
  let index2 = numbers.length - 1
  while (index1 < index2) {
    if (numbers[index1] + numbers[index2] > target) {
      index2--
    } else if (numbers[index1] + numbers[index2] < target) {
      index1++
    } else {
      return [index1 + 1, index2 + 1]
    }
  }
}

/**
 * 与第一题类似的方法
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
export var twoSum2 = function (numbers, target) {
  const map = new Map()
  for (let i = 0; i < numbers.length; i++) {
    if (map.has(numbers[i])) {
      return [map.get(numbers[i]) + 1, i + 1]
    } else {
      map.set(target - numbers[i], i)
    }
  }
}

/**
 * 二分查找 虽为O(n log n) 但是比在提交的测试用例中，比方法一快
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
export var twoSum3 = function (numbers, target) {
  const ans = []
  for (let i = 0; i < numbers.length; i++) {
    const num = numbers[i]
    const diff = target - num
    let [left, right] = [i + 1, numbers.length - 1]
    let tempAns = -1
    while (left <= right) {
      const mid = (left + right) >> 1
      if (numbers[mid] === diff) {
        tempAns = mid
        break
      }
      if (numbers[mid] < diff) left = mid + 1
      else right = mid - 1
    }
    if (tempAns !== -1) {
      ans.push(i + 1, tempAns + 1)
      break
    }
  }
  return ans
}
